# -*- coding:utf-8 -*-

'''
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
'''

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        self.next = None

class Solution:
    def GetNext(self, node):
        # write code here
        # 首先判断该节点有没有右孩子
        if node.right is not None:
            res = self.inorder(node.right)
            return res[0]
        # 在判断他是他父节点的左孩子还是右孩子
        if node.next is not None:
            father = node.next
            # node是父亲的左孩子
            if father.left == node:
                return father
            #node是父亲的右孩子，那么沿着指向父节点的指针一直向上遍历直到找到一个是
            # 它父节点的左孩子的节点。
            else:
                while father.next != None and father.left != node:
                    node = father
                    father = node.next
                if father.left == node:
                    return father
        return None

    #中序遍历
    def inorder(self, root):
        if root is None:
            return []
        res = []
        res += self.inorder(root.left)
        res.append(root)
        res += self.inorder(root.right)
        return res

pNode1 = TreeNode(8)
pNode2 = TreeNode(6)
pNode3 = TreeNode(10)
pNode4 = TreeNode(5)
pNode5 = TreeNode(7)
pNode6 = TreeNode(9)
pNode7 = TreeNode(11)

pNode1.left = pNode2
pNode1.right = pNode3
pNode2.left = pNode4
pNode2.right = pNode5
pNode3.left = pNode6
pNode3.right = pNode7

test = Solution()
nextNode = test.GetNext(pNode1).val
print(nextNode)